#ifndef _SCUDB_TTREE_H_
#define _SCUDB_TTREE_H_

#include "sd_global.h"
#include "sd_thread.h"
#include "sd_oplog.h"
#include "sd_hashtable.h"

struct sd_TTree;

typedef struct sd_TTreeNode
{
	struct sd_TTree* tree;
	sd_uid id; /* Node ID */
	struct sd_TTreeNode* parent;
	struct sd_TTreeNode* leftChild;
	struct sd_TTreeNode* rightChild;
	int depth;
	sd_RWLock lock; /* The lock to protect the records of this node */
	size_t numRecords;
	sd_Record records[1];
}sd_TTreeNode;

typedef struct sd_TTree
{
	sd_uid treeId;
	sd_KeyCompare key_cmp;
	size_t maxNumRecordsOfNode;
	sd_uid nodeIdCounter;
	int depth;
	sd_SpinLock lock; /* The lock to the structure of this tree */
	sd_SpinLock tidLock;
	sd_Hashtable* nodeLockTable; /* To record all locked nodes for debugging the deadlock */
	sd_TTreeNode* rootNode;
}sd_TTree;

sd_Ret sd_TTreeCreate(sd_TTree** tree, size_t maxRecOfNode, sd_KeyCompare key_cmp);
sd_Ret sd_TTreeFree(sd_TTree* tree);
sd_Ret sd_TTreeInsert(sd_TTree* tree, const sd_Record* record);
sd_Ret sd_TTreeGetFirst(sd_TTree* tree, sd_Record* record);
sd_Ret sd_TTreeSearch(sd_TTree* tree, const sd_Key* key, sd_Record* record);
sd_Ret sd_TTreeSearchNext(sd_TTree* tree, const sd_Record* preRecord, sd_Record* record);
sd_Ret sd_TTreeSearchRID(sd_TTree* tree, sd_Record* record, sd_uid* rid);
sd_Ret sd_TTreeDelete(sd_TTree* tree, const sd_Record* record);
sd_Ret sd_TTreePrint(sd_TTree* tree, FILE* fp);
sd_Ret sd_TTreeCheck(sd_TTree* tree);








#endif
